n=2000;
m=1;
road=[|250,1494,838|
537,1817,65|
1457,249,786|
392,532,696|
464,284,728|
31,1166,37|
8,229,717|
3,935,222|
766,1477,51|
1462,369,665|
1187,448,54|
397,158,608|
1544,479,152|
1345,1162,949|
1048,1266,125|
1742,1466,737|
322,1924,89|
549,1108,311|
454,563,827|
1868,1286,582|
1501,1504,108|
1703,825,233|
1670,1943,508|
556,1902,791|
1121,972,476|
706,325,303|
1327,727,111|
856,595,861|
316,1715,96|
118,1594,355|
1694,1675,667|
1607,874,910|
1183,776,761|
1373,263,183|
1419,1012,170|
1302,963,983|
542,1934,422|
19,1480,447|
1881,437,438|
656,1390,328|
1146,794,553|
1075,1371,18|
104,717,294|
105,1139,291|
555,941,596|
1837,172,218|
1593,1243,17|
978,1208,907|
1900,340,169|
694,657,177|
587,375,339|
1729,1215,817|
51,1435,323|
196,17,454|
861,929,194|
612,1612,841|
1578,64,822|
128,842,262|
1968,1988,980|
689,1106,260|
134,1568,195|
204,322,854|
1538,378,157|
82,1034,588|
420,895,295|
1521,368,450|
705,1020,92|
1660,775,127|
1812,808,63|
813,1522,639|
1009,323,189|
1504,797,926|
223,940,268|
795,1906,98|
373,531,377|
1957,139,127|
860,621,821|
678,714,379|
1030,923,684|
769,238,641|
597,1413,691|
467,63,309|
1602,1922,825|
270,1052,2|
1032,188,249|
1666,809,889|
1352,1790,319|
40,61,113|
995,305,430|
1052,530,907|
1658,962,706|
1973,364,319|
140,857,374|
1690,861,398|
519,1526,830|
1672,170,842|
500,184,418|
645,1043,329|
1051,748,876|
895,1826,126|
1360,1580,791|
714,1302,962|
750,1297,823|
609,1872,866|
1168,585,132|
1113,493,232|
279,1440,10|
624,1500,891|
631,458,311|
1647,152,584|
641,1396,619|
674,311,787|
78,1626,686|
881,503,748|
1747,1540,867|
1005,1530,77|
1355,1520,881|
552,1899,16|
1348,419,759|
1384,186,128|
859,1116,915|
713,1758,266|
804,1281,878|
1866,1024,512|
1164,1752,47|
1015,88,486|
1916,1091,365|
423,247,565|
1947,351,689|
1885,1854,771|
370,801,695|
1107,1563,686|
1892,1071,403|
1616,1097,968|
430,1086,296|
627,1126,351|
685,1663,817|
997,1544,967|
1106,1856,986|
1682,376,197|
1563,1235,505|
379,433,193|
1319,1409,105|
152,1752,407|
1253,1308,321|
797,1750,561|
61,1562,142|
1332,692,319|
443,841,0|
1394,737,749|
1187,1167,121|
823,1956,436|
324,1068,339|
1207,743,552|
702,882,189|
140,481,108|
1942,585,145|
617,146,100|
445,652,124|
306,83,29|
922,106,992|
163,733,97|
340,177,352|
1060,1683,78|
565,1846,792|
898,137,993|
897,776,589|
1598,866,63|
1244,829,589|
1198,1799,836|
1624,713,954|
1566,113,561|
455,1246,751|
1889,1021,295|
1547,389,54|
1695,1181,927|
673,477,975|
341,610,860|
1726,267,843|
1328,1068,961|
1842,1769,398|
971,367,667|
561,1534,884|
357,1766,247|
880,1882,88|
117,1469,248|
1894,372,572|
1172,120,273|
1666,510,132|
303,1173,773|
1650,1301,825|
525,504,426|
1149,181,679|
1451,86,779|
912,168,200|
1011,122,610|
1725,1017,150|
421,801,666|
209,1326,444|
1659,661,754|
828,41,425|
364,1618,487|
834,454,227|
1664,1431,854|
505,236,970|
338,1671,802|
902,1576,927|
769,1659,309|
1762,988,505|
513,490,994|
332,548,709|
189,814,882|
1908,24,541|
709,706,436|
1914,1643,729|
1191,1182,287|
1025,601,353|
591,1091,783|
831,677,145|
817,226,348|
1293,1498,917|
154,174,114|
461,722,61|
502,718,5|
295,634,152|
977,1029,677|
1738,655,63|
490,1007,181|
867,998,760|
982,1267,960|
1708,1425,319|
761,613,402|
246,1298,363|
96,1128,525|
907,577,615|
34,1836,272|
1606,1869,12|
1774,1984,780|
768,284,322|
352,42,396|
965,257,662|
21,954,426|
1818,265,151|
659,259,453|
992,928,54|
1710,1009,674|
37,1485,89|
1353,1800,937|
713,1434,638|
693,459,700|
1590,1747,642|
1174,925,71|
1090,1948,396|
538,446,165|
874,406,70|
844,1981,537|
359,1030,30|
208,369,441|
56,1819,711|
1338,477,784|
424,1732,394|
1147,1766,361|
176,490,869|
1946,551,374|
860,243,103|
1866,871,949|
598,150,810|
300,1115,624|
1770,929,180|
1967,1805,662|
255,115,666|
637,713,39|
1359,438,979|
1157,1776,129|
1867,422,967|
876,289,259|
1781,77,22|
697,1989,280|
331,1418,777|
462,1798,707|
99,1458,429|
148,116,134|
296,536,413|
1777,786,660|
315,280,469|
1394,163,141|
1372,1217,356|
615,171,795|
1428,1977,904|
1487,6,222|
295,1237,144|
525,579,333|
394,174,793|
1719,302,694|
569,1816,180|
1400,1341,893|
1002,1678,158|
1592,1003,919|
1663,1831,371|
1774,18,147|
886,1488,357|
1314,1642,806|
85,746,461|
646,327,933|
1307,826,348|
142,96,773|
780,1446,57|
47,1120,6|
1463,23,346|
1269,1354,121|
1465,226,633|
1691,1886,293|
1644,1769,438|
1118,2000,655|
57,845,253|
1192,304,959|
506,1639,455|
552,841,855|
1098,234,113|
693,61,72|
434,1566,522|
280,1354,464|
22,1831,254|
880,1052,232|
953,506,116|
1515,1228,705|
1407,1765,174|
748,1567,188|
980,36,407|
491,853,273|
1950,290,912|
653,1177,724|
1315,1985,711|
1386,1478,599|
1563,669,978|
366,564,990|
296,945,102|
1380,1384,891|
1496,987,35|
1744,203,206|
1809,1558,677|
104,1090,819|
996,1980,954|
1064,1334,162|
546,1748,18|
1382,1497,798|
1608,916,765|
256,757,918|
695,384,845|
418,648,109|
1023,507,563|
1841,156,698|
1509,1830,983|
1874,976,190|
1728,811,256|
563,94,816|
1418,806,776|
865,873,757|
46,1473,913|
1466,1728,189|
419,1376,84|
342,824,152|
1501,915,151|
547,506,671|
1660,1193,576|
50,1836,93|
1073,1771,483|
472,793,790|
667,1126,547|
400,1658,964|
1536,920,448|
1938,1964,748|
619,238,164|
989,730,143|
1016,482,16|
233,529,316|
140,795,75|
1537,827,431|
634,509,388|
1201,1141,33|
1738,70,121|
1931,1048,911|
1184,1731,991|
1019,95,659|
751,1868,683|
207,1389,364|
588,356,101|
463,1526,286|
1945,717,38|
959,1027,933|
736,808,604|
1757,1158,713|
1137,877,882|
830,1337,112|
885,1599,174|
1402,925,988|
1431,1297,963|
367,384,664|
1170,1220,218|
659,642,300|
1113,156,29|
1689,1271,534|
1895,1048,302|
145,1954,928|
1637,1665,955|
1682,1015,372|
261,1125,22|
377,1950,381|
362,1954,450|
1828,1668,444|
526,833,53|
1310,215,572|
250,274,921|
1847,891,175|
734,1399,136|
447,1595,946|
276,1204,976|
1874,1216,658|
1443,168,629|
1734,638,176|
272,942,15|
1300,1858,989|
1898,334,550|
1210,637,7|
379,1778,886|
1246,468,5|
325,1505,7|
1102,959,295|
1285,1544,108|
395,1555,880|
707,608,703|
278,553,559|
1848,1623,185|
478,887,478|
1428,377,889|
1826,1637,723|
157,873,954|
433,958,728|
1929,1304,251|
1864,198,76|
967,1325,568|
1296,1625,966|
1749,1434,521|
993,1060,31|
1448,1166,458|
194,1501,542|
1100,1461,4|
928,949,255|
1276,1697,581|
1178,763,259|
1975,1293,320|
1633,907,182|
810,1836,335|
595,1622,894|
993,660,995|
663,1832,759|
1516,1722,162|
1376,998,760|
407,326,903|
790,1524,836|
1833,700,123|
1539,1656,314|
234,1095,132|
743,601,611|
1438,1036,207|
1810,1842,859|
1605,1590,946|
1094,962,793|
368,1299,122|
967,1122,961|
945,1670,641|
1853,1933,207|
446,1275,912|
362,812,912|
1280,1276,548|
1759,556,223|
1445,667,657|
368,1102,627|
1525,1305,499|
628,1507,287|
1309,85,95|
1650,1646,876|
1619,1132,86|
188,453,200|
1795,1026,162|
15,1366,139|
307,1439,566|
1510,1058,633|
1247,1846,881|
754,1112,572|
1905,159,812|
767,507,512|
1781,803,183|
1546,1596,839|
1343,237,152|
145,1317,453|
1182,87,75|
672,1468,708|
1962,366,479|
138,1855,638|
694,417,56|
1110,435,836|
1642,1017,66|
1997,956,872|
1857,1932,863|
45,907,708|
495,559,385|
908,69,268|
1830,1512,968|
1161,1827,187|
1788,1539,966|
680,924,116|
20,399,945|
620,1724,811|
699,1267,69|
1092,821,956|
1348,492,999|
499,1800,948|
370,406,467|
1936,1527,392|
187,1808,378|
664,741,518|
503,488,285|
1344,1432,844|
385,403,605|
1369,1055,624|
545,1477,854|
1726,405,835|
1543,1347,779|
464,1878,604|
323,1227,715|
1854,496,479|
859,1951,226|
791,615,833|
1877,592,81|
602,504,155|
1612,1076,682|
1482,1754,317|
1393,112,677|
864,1581,544|
807,1531,257|
205,831,288|
391,514,502|
925,1056,670|
408,1436,796|
1291,1138,574|
217,1423,99|
782,146,961|
533,476,224|
139,204,486|
1470,1751,431|
1696,1631,430|
1127,762,572|
1222,551,399|
310,1223,188|
1087,1666,343|
1967,33,69|
1220,1476,498|
844,1077,501|
647,1331,692|
999,957,964|
242,578,469|
914,1775,372|
1853,1634,494|
135,1857,68|
1332,678,730|
1925,703,730|
80,1475,122|
59,1842,920|
24,254,950|
457,1590,355|
1487,281,251|
1994,1046,242|
1601,1111,36|
1153,1405,424|
543,1503,533|
320,114,972|
143,332,523|
211,1868,746|
589,1841,372|
733,581,942|
757,1569,797|
439,670,713|
779,109,939|
73,63,791|
294,1024,134|
1764,398,899|
839,776,866|
1333,444,507|
1552,1208,600|
1415,618,131|
1078,611,336|
1149,825,657|
111,1055,724|
583,293,795|
653,568,97|
1832,892,37|
117,989,573|
1682,435,214|
1222,917,559|
1904,1379,120|
618,15,604|
1334,979,37|
1079,1575,782|
969,156,68|
1887,404,342|
1776,1772,265|
640,43,362|
1721,1261,743|
1261,1730,854|
1118,156,673|
167,411,133|
386,443,646|
1719,1979,21|
1641,1598,81|
1761,1246,620|
789,1088,90|
1080,208,288|
217,1442,715|
1346,626,156|
129,307,459|
1896,1069,612|
1597,1770,183|
786,1517,763|
904,218,25|
1155,1920,504|
1900,1835,839|
879,23,465|
1709,87,531|
1766,1930,146|
1186,243,868|
974,1240,775|
747,965,316|
1561,1135,712|
1392,1371,957|
478,410,856|
1000,1101,763|
383,1464,953|
441,230,622|
754,1237,559|
804,634,760|
560,181,890|
881,1199,361|
1976,600,540|
1212,1020,969|
768,807,446|
815,1753,938|
1608,14,889|
1465,1511,656|
232,1310,227|
152,340,790|
664,1250,447|
39,323,619|
1853,1633,364|
683,924,173|
528,1165,557|
572,950,508|
861,1420,380|
1474,1272,615|
1629,845,479|
1107,1543,468|
570,927,261|
1334,252,903|
960,1693,779|
133,1205,127|
1871,385,479|
1294,1787,616|
890,650,789|
1662,1189,971|
520,986,309|
243,1630,40|
500,436,662|
446,1251,202|
796,756,131|
180,1725,873|
1840,1404,622|
1922,748,80|
1037,1421,52|
1880,532,543|
1447,1934,880|
1207,1966,12|
1987,891,310|
1577,1927,444|
356,723,925|
888,98,98|
1717,1219,378|
291,637,135|
1763,59,785|
1801,1838,808|
804,894,834|
438,219,423|
1358,1937,748|
284,183,410|
1554,1219,375|
1949,1952,729|
269,714,959|
581,115,660|
1905,489,751|
1631,1036,384|
819,1733,449|
227,1083,291|
38,677,242|
1133,1756,927|
1273,1670,552|
505,165,515|
1217,911,918|
1786,1611,284|
785,961,179|
402,1042,531|
1859,408,355|
1739,947,11|
960,970,333|
107,1469,578|
1096,80,50|
992,239,840|
929,802,299|
151,622,226|
1256,1702,249|
394,371,564|
348,1782,644|
285,1856,118|
71,1005,307|
1247,1114,648|
859,1652,168|
1865,69,850|
985,1852,527|
1968,765,346|
1389,1459,830|
858,363,268|
760,52,914|
677,1716,132|
227,158,713|
299,596,85|
1937,150,810|
832,1141,698|
1248,140,397|
890,540,21|
1998,1968,284|
1385,317,153|
1522,437,926|
1311,1838,278|
1853,1571,386|
1021,337,687|
1155,1890,823|
933,401,39|
1097,1579,730|
1362,134,254|
838,1800,659|
1495,91,941|
1873,287,171|
1721,26,129|
333,946,310|
51,668,698|
727,1636,907|
1338,1341,255|
64,938,762|
202,559,872|
746,962,302|
1403,1059,584|
946,1340,781|
1917,1385,785|
159,1885,517|
1133,363,48|
1331,899,118|
1234,1497,428|
508,1047,433|
191,788,551|
122,91,327|
951,82,384|
1197,1952,979|
1992,334,179|
1421,1554,504|
1569,1654,555|
521,1490,156|
1020,987,652|
445,858,626|
1404,175,441|
153,760,454|
162,1459,956|
11,203,30|
1517,961,329|
1649,383,470|
1883,530,418|
310,216,548|
851,1047,629|
1514,937,293|
646,1927,854|
1514,1296,732|
1628,303,3|
1150,1304,854|
1759,611,648|
1528,329,473|
1837,1662,54|
1934,473,193|
1008,179,970|
931,503,630|
371,1617,641|
1635,340,122|
1305,760,658|
1194,402,195|
217,183,450|
263,544,709|
429,1492,809|
1972,1381,420|
1424,1464,958|
1175,727,281|
1638,1255,443|
1081,879,775|
701,1378,380|
1305,170,628|
1231,528,590|
484,1737,518|
167,260,908|
412,1659,256|
941,323,694|
984,1704,200|
700,339,991|
1110,753,497|
484,724,104|
517,1403,13|
314,1342,140|
537,952,485|
188,1652,616|
837,794,351|
429,905,725|
873,1142,364|
45,223,535|
663,1559,978|
81,1806,112|
230,1351,420|
1044,968,344|
336,888,573|
870,624,774|
1452,1955,601|
736,531,64|
374,190,406|
1160,1020,748|
1005,1803,721|
1277,224,12|
1403,1626,781|
247,968,190|
1936,1023,444|
981,158,297|
1491,236,198|
639,710,362|
142,1609,84|
440,1317,919|
1596,520,464|
1548,865,195|
329,1748,965|
110,844,665|
1464,1961,72|
1875,1122,364|
178,1707,632|
1189,1647,539|
1181,1062,866|
1111,1654,877|
712,1688,363|
889,401,770|
319,1117,637|
150,287,227|
1629,1028,727|
1336,1071,871|
577,1538,790|
73,1278,716|
387,553,592|
6,1720,61|
316,287,188|
1572,1720,982|
1995,1255,213|
1879,1714,825|
1350,828,331|
1681,1983,387|
16,500,153|
67,1239,787|
1399,324,513|
734,246,634|
830,31,860|
1614,324,787|
1441,459,694|
706,1888,784|
960,41,291|
1938,728,324|
131,226,628|
1323,577,872|
1646,1734,115|
1465,1279,410|
868,703,337|
991,1626,152|
919,148,415|
1640,68,247|
432,1984,16|
1515,72,711|
128,112,608|
1308,1033,21|
1993,61,713|
1045,326,248|
1432,257,400|
838,1414,262|
25,1706,861|
288,1375,727|
206,317,92|
1784,1324,390|
800,1127,198|
1409,433,593|
141,126,887|
370,1312,74|
673,166,607|
1426,1006,808|
1580,13,704|
1966,1240,469|
1620,573,584|
516,388,306|
1742,672,448|
231,1575,554|
173,1621,867|
1504,1586,142|
1574,1743,988|
1604,740,704|
1848,1260,322|
1260,331,405|
49,1903,39|
628,21,92|
644,1509,605|
1634,1496,547|
344,1211,968|
149,1581,613|
1404,1923,812|
1282,440,888|
1873,705,695|
1553,405,45|
1582,877,47|
1493,1560,273|
1429,1412,18|
1292,729,387|
1472,1426,926|
632,1250,970|
920,1539,376|
810,897,787|
1230,571,892|
1352,1264,889|
1330,314,522|
970,130,475|
485,1661,994|
1740,651,12|
975,220,236|
559,485,69|
1391,1116,217|
872,537,581|
1743,1766,331|
603,458,588|
1565,1298,179|
1824,43,111|
515,1924,133|
651,815,53|
801,1395,803|
1817,172,886|
1818,961,941|
244,1269,902|
721,1297,567|
1651,592,918|
335,1690,419|
1206,1178,954|
468,263,645|
802,102,536|
1624,185,943|
1014,1645,224|
1040,1881,789|
477,255,364|
1610,1847,445|
1574,18,799|
554,660,721|
1148,1861,771|
464,716,815|
1736,815,299|
1705,403,975|
1262,1661,846|
1845,920,840|
1409,206,952|
1096,1453,916|
692,617,478|
1092,1816,161|
755,730,334|
1781,1328,252|
1795,599,809|
730,1,858|
270,1447,723|
501,1453,264|
1676,843,442|
352,1370,449|
694,1293,948|
1671,290,700|
1066,131,152|
962,1080,366|
1413,139,568|
107,682,671|
623,465,56|
1706,1158,570|
1705,1061,669|
708,1067,183|
1976,843,711|
1456,352,345|
335,547,235|
826,1316,191|
1587,1485,72|
209,1021,849|
67,576,454|
1962,1728,130|
1136,74,362|
855,1450,300|
476,1879,709|
1944,1345,70|
1494,855,82|
393,1945,112|
772,752,252|
1746,1678,144|
1970,329,48|
575,700,112|
1140,1856,530|
676,1411,743|
111,1155,539|
606,52,682|
1098,1677,320|
1200,732,278|
365,1609,412|
522,347,283|
94,1364,279|
673,1669,476|
1310,1540,184|
1456,1912,586|
926,1940,939|
1287,557,204|
1956,1329,831|
1191,1187,931|
135,1657,780|
449,439,833|
1180,580,384|
1267,834,762|
684,109,356|
1270,1231,512|
1867,644,468|
1668,1530,297|
1732,1059,461|
1288,176,92|
1681,1723,964|
875,846,795|
714,764,787|
482,1142,460|
1413,1287,287|
1751,1765,704|
679,71,413|
1159,1524,911|
661,1573,38|
1537,1260,965|
750,1580,599|
27,1941,903|
1091,627,54|
1179,789,831|
1713,1432,581|
1089,1010,446|
968,725,225|
683,344,648|
132,99,920|
149,1654,725|
1640,301,829|
1252,1629,828|
7,1011,730|
1238,876,401|
1311,1812,854|
848,787,653|
630,485,310|
1672,1014,782|
52,1986,817|
931,72,392|
1363,204,672|
483,1949,541|
1035,601,402|
1786,491,668|
850,1981,565|
1212,747,637|
1047,5,583|
1535,1236,140|
669,1707,931|
19,855,341|
936,1449,423|
1315,497,283|
1062,781,348|
576,474,645|
1221,1905,198|
1084,737,128|
511,1085,727|
1987,604,304|
1419,1393,263|
701,655,142|
1265,60,3|
1741,1173,611|
1491,715,281|
102,1138,915|
777,875,315|
450,1624,393|
1561,1774,330|
906,597,240|
1212,53,891|
1116,1449,409|
142,213,27|
387,1306,143|
825,380,162|
1712,921,37|
1892,607,61|
992,719,845|
514,502,755|
469,148,112|
131,693,106|
277,71,433|
487,1013,770|
1452,1382,502|
49,1478,85|
332,1847,633|
1728,202,442|
666,1243,548|
1284,1126,970|
715,1205,639|
253,740,134|
1711,812,223|
1357,746,230|
1109,875,741|
837,1824,130|
1368,696,2|
1724,1041,382|
1215,1551,454|
10,1869,402|
313,1052,727|
29,1089,862|
84,1804,184|
527,1032,585|
1746,1938,191|
1322,1231,515|
251,35,762|
310,427,582|
860,49,528|
1214,274,201|
1145,1352,147|
1622,1205,169|
850,738,116|
1111,1343,178|
784,1636,746|
259,4,202|
82,722,21|
768,1716,714|
1541,817,297|
447,1703,786|
17,623,295|
455,1566,818|
93,1185,619|
4,333,413|
1173,1983,326|
1792,1274,552|
1794,121,964|
304,302,563|
853,1988,896|
1775,544,415|
849,932,897|
425,267,359|
212,1290,201|
1918,924,482|
794,460,145|
416,848,259|
266,216,688|
1287,1935,939|
1105,1818,511|
1749,1157,549|
613,1506,342|
876,41,449|
1977,125,419|
1419,452,465|
1791,562,707|
1699,1813,670|
885,353,820|
1915,873,333|
1461,1534,760|
893,190,295|
1195,244,907|
1891,792,145|
1991,1753,369|
542,1115,60|
624,1653,244|
1484,1585,531|
1044,510,85|
1583,1319,914|
28,1798,46|
447,154,647|
80,365,951|
1709,978,791|
777,854,596|
799,533,783|
1820,1825,575|
866,707,981|
1823,350,643|
1129,366,635|
996,1233,897|
618,1928,234|
1306,1996,716|
19,1144,801|
384,1290,524|
1045,1061,913|
1701,145,269|
514,1680,627|
1843,754,511|
195,1680,265|
1712,1135,267|
1072,839,909|
1704,1397,356|
1391,1718,645|
1471,167,639|
812,1663,1000|
46,42,492|
349,942,95|
862,762,396|
1109,99,705|
1159,1698,562|
121,1169,152|
1745,1252,925|
230,1977,991|
1188,229,589|
76,7,668|
506,864,274|
1884,1079,619|
1419,1739,462|
428,1577,998|
648,235,873|
1773,617,762|
386,589,996|
410,1760,460|
1754,1907,545|
730,990,977|
1319,197,824|
1737,69,957|
138,691,445|
179,826,99|
164,27,699|
477,708,188|
1192,1440,832|
763,726,925|
1852,848,807|
739,706,586|
390,1408,376|
663,1176,76|
704,179,406|
726,1881,143|
1767,1917,734|
16,1283,837|
1921,1471,721|
1864,396,236|
1543,781,596|
1064,471,647|
1386,1263,54|
1203,79,826|
594,504,603|
1074,272,592|
470,852,766|
655,1086,356|
1293,818,157|
396,191,744|
1546,561,680|
321,1403,218|
1218,1514,571|
1799,605,50|
171,1258,411|
1682,1335,158|
1014,395,484|
1817,123,181|
1241,501,259|
354,1002,137|
1304,1904,410|
1002,242,514|
868,406,801|
1956,1161,699|
921,1271,93|
1446,1387,917|
917,1220,981|
1866,610,374|
1578,1229,873|
1733,1754,55|
524,18,219|
214,1139,117|
221,193,755|
1545,1370,537|
1421,1556,746|
1664,1674,860|
264,1043,43|
278,511,786|
501,1376,99|
1437,1704,19|
889,1499,668|
376,584,338|
1938,1901,691|
1767,1671,326|
1797,474,978|
44,1636,598|
540,1393,193|
330,243,532|
1755,1906,149|
1263,625,547|
574,1493,100|
442,1041,562|
770,1954,23|
720,566,213|
530,1542,836|
827,491,27|
1847,688,75|
535,1969,179|
868,1598,851|
1073,1410,703|
1444,882,331|
863,322,864|
1237,619,684|
199,526,494|
1975,461,774|
592,1495,580|
1912,836,846|
1816,752,465|
282,1017,421|
396,319,682|
1224,9,757|
1901,888,478|
1771,1225,987|
1627,216,654|
1697,171,237|
1375,275,498|
994,1521,113|
697,558,444|
335,1416,877|
1851,1090,453|
1308,999,427|
517,1845,715|
314,31,221|
835,986,228|
483,1164,158|
482,588,938|
101,525,916|
1530,1829,446|
523,1999,125|
498,1320,837|
1870,713,207|
558,185,712|
355,414,145|
2,1351,501|
1369,161,951|
1769,1924,748|
1570,1392,206|
1050,286,361|
1518,1156,416|
258,691,638|
1069,1407,44|
1627,567,491|
89,1625,348|
1230,738,495|
1762,283,113|
586,1891,202|
43,382,836|
164,1374,478|
1281,1435,827|
1492,1488,88|
1513,1980,806|
771,480,120|
947,1101,289|
612,1549,525|
520,296,153|
1427,624,745|
169,1502,295|
666,816,314|
513,1489,817|
1813,1637,506|
599,1942,248|
1238,173,324|
745,175,151|
32,721,815|
752,942,443|
1372,219,81|
955,407,719|
1383,1586,19|
1673,1982,795|
182,900,127|
1860,1188,287|
1025,1072,504|
1349,1708,126|
1422,813,520|
586,271,478|
1367,139,973|
94,1239,828|
512,1813,957|
1041,862,754|
919,871,68|
1053,1120,178|
708,1018,580|
1722,1734,976|
292,1198,973|
1172,135,999|
1789,310,395|
1494,1963,94|
187,773,673|
913,1470,10|
854,299,537|
160,516,734|
810,912,809|
360,1053,965|
1513,97,526|
1914,361,794|
162,268,819|
1582,610,356|
268,1959,319|
1838,122,978|
1162,1958,486|
1536,1749,347|
1349,1436,823|
1281,1325,205|
802,1685,730|
415,287,816|
26,1211,808|
1584,710,789|
136,1194,390|
741,1993,98|
1596,400,258|
629,10,557|
857,613,749|
1436,497,612|
629,527,937|
1163,1303,493|
1396,658,606|
1741,1789,805|
1560,442,794|
1377,160,539|
1604,1403,947|
221,4,551|
1996,1249,346|
1597,1621,95|
832,1001,334|
1589,1465,6|
178,687,270|
973,426,102|
837,1364,285|
575,1224,887|
647,1338,755|
1875,1121,777|
115,562,244|
546,1377,307|
922,1246,394|
805,599,793|
1646,1518,271|
1261,1242,444|
651,1196,797|
948,763,256|
1082,215,297|
1938,399,298|
1630,452,553|
361,1033,177|
1029,1470,555|
114,106,618|
1046,981,639|
1022,86,880|
235,1187,16|
1787,1524,512|
1822,908,130|
909,1783,82|
37,944,490|
355,685,906|
903,1573,562|
1175,604,848|
976,1039,978|
1618,205,918|
1143,430,867|
888,918,394|
1471,1811,728|
1460,433,477|
367,1253,196|
1433,460,983|
1435,1105,537|
1188,1049,877|
1785,677,653|
371,692,402|
684,1117,392|
1320,1762,880|
950,1250,81|
309,233,669|
1679,1845,709|
130,1909,547|
1493,1646,946|
534,1380,87|
600,1176,946|
1108,1484,560|
1148,1381,184|
1424,1916,180|
1119,941,524|
943,312,3|
538,1589,841|
1735,1721,620|
1769,691,961|
819,1821,796|
1123,738,915|
456,200,185|
1854,832,927|
1780,1834,967|
1947,411,783|
135,1206,597|
60,947,658|
1550,1897,109|
709,879,230|
436,1180,498|
744,263,936|
303,1190,181|
613,1727,808|
347,1030,318|
1850,1472,416|
194,539,562|
66,338,627|
1331,943,862|
788,1074,62|
58,900,327|
1820,886,155|
1952,494,470|
1384,1065,671|
413,1235,164|
1483,1431,788|
786,1960,335|
416,1430,283|
620,1095,880|
1921,1683,508|
1782,249,945|
1855,1913,789|
1347,1339,906|
1608,211,794|
1775,293,623|
119,260,207|
353,1796,254|
1824,898,8|
1549,687,153|
995,367,510|
401,729,17|
656,862,774|
1565,951,345|
1181,1350,493|
440,560,951|
447,1594,529|
1389,1408,935|
1700,1044,999|
216,1152,279|
472,439,714|
735,847,340|
343,88,967|
979,1268,550|
1295,1151,162|
994,1858,307|
1797,1691,408|
1450,1978,200|
1232,1108,155|
1166,1372,255|
882,1064,348|
222,398,564|
632,1322,421|
1349,1834,584|
92,297,45|
674,966,399|
1199,1294,328|
469,383,32|
1015,1532,299|
12,1529,200|
1984,774,944|
472,1719,905|
1685,1507,754|
1104,1717,38|
1919,1835,859|
1804,945,64|
1289,1945,867|
422,1316,649|
605,711,452|
237,989,811|
582,1426,342|
662,920,490|
939,1610,18|
1692,1502,378|
56,928,849|
724,671,438|
720,1398,680|
1733,1610,307|
1809,1906,134|
1165,1710,742|
1579,1910,187|
164,1726,182|
1113,248,485|
1760,276,902|
1884,301,893|
1266,336,725|
756,844,979|
1205,426,927|
1615,1218,891|
888,1375,766|
318,738,238|
633,679,964|
902,641,856|
1684,1559,212|
1972,210,157|
147,1827,61|
197,1586,760|
1550,238,215|
789,1863,934|
1523,801,708|
674,414,679|
199,1405,518|
1346,662,260|
90,1006,473|
730,1299,211|
1303,896,342|
1520,35,581|
1348,1247,574|
946,1447,569|
1003,1130,848|
665,678,607|
1625,1339,966|
663,1388,238|
666,568,236|
519,35,980|
95,1805,920|
471,158,413|
1858,273,26|
1466,475,383|
523,627,192|
1166,1974,391|
139,636,350|
718,976,158|
1014,222,389|
646,1872,216|
1783,1876,297|
1839,1609,198|
872,1894,304|
929,75,608|
406,1406,468|
927,1978,804|
1564,476,227|
431,260,232|
376,1195,356|
1197,1593,581|
900,290,587|
1744,901,321|
210,1808,756|
1358,214,93|
1528,1591,720|
1176,225,839|
745,77,157|
441,1570,172|
550,119,96|
696,932,95|
980,1481,449|
292,225,136|
1944,759,483|
191,1284,16|
1967,1132,865|
780,1808,537|
988,1464,729|
1792,1946,828|
1535,1274,535|
1128,1274,139|
157,604,5|
1815,2,503|
1220,1313,504|
1418,10,858|
690,1216,802|
6,1303,123|
1087,1959,126|
516,1667,8|
227,1725,961|
215,1285,28|
944,1807,745|
840,410,695|
1103,643,402|
526,1050,717|
686,980,977|
1370,32,819|
477,1356,451|
1417,1188,891|
1098,136,587|
701,298,753|
1134,431,143|
1090,1922,328|
1641,1852,916|
421,1687,104|
1681,1230,246|
1458,1196,748|
1120,884,587|
1097,1264,389|
1557,1924,412|
1691,342,771|
186,1063,867|
573,1557,409|
955,450,196|
1508,88,376|
1070,1659,665|
484,240,679|
1946,189,168|
1051,971,24|
1829,1123,83|
451,1665,433|
1920,228,350|
1078,1510,302|
977,1414,224|
578,1814,33|
616,869,628|
731,957,789|
428,1955,588|
389,1736,546|
307,42,210|
966,794,864|
148,169,795|
328,486,378|
1429,1802,395|
1218,829,679|
14,1037,686|
959,345,711|
631,1830,707|
1674,1554,444|
1632,1355,871|
1849,561,524|
1559,489,507|
300,934,760|
1513,1000,252|
1110,1860,494|
1941,1703,98|
1602,1503,649|
126,1236,38|
1689,1278,600|
352,556,706|
480,55,43|
1970,846,789|
399,580,581|
403,1397,844|
1929,1884,979|
1057,317,564|
940,211,737|
467,778,229|
1768,1740,280|
276,686,150|
518,633,749|
1757,34,497|
1472,1626,894|
1600,984,997|
487,396,502|
582,201,298|
394,37,981|
1793,1939,888|
252,1558,241|
325,812,662|
679,445,939|
1003,869,623|
1264,1152,654|
747,1047,106|
1919,1863,499|
570,546,538|
909,264,738|
140,1648,337|
973,1665,238|
1893,1151,887|
309,593,112|
1144,1345,340|
1278,1844,392|
437,582,279|
508,822,532|
57,1168,790|
765,1455,614|
1992,1442,132|
1862,1648,807|
1200,1813,658|
964,355,965|
583,1794,427|
749,1103,321|
1686,1498,250|
545,144,948|
1410,1072,260|
1895,1490,799|
1220,1718,30|
423,1826,175|
1568,1709,127|
1446,1731,950|
1980,1632,424|
1103,1887,343|
447,930,554|
1019,1655,710|
1272,131,459|
1395,1065,313|
1945,541,84|
238,742,207|
1270,1396,203|
975,914,948|
1167,1021,310|
1408,1683,243|
1451,358,946|
597,1895,207|
1257,592,353|
1898,1736,958|
1861,1193,579|
1973,1467,166|
838,1226,672|
427,1398,586|
606,235,884|
564,951,506|
110,1971,399|
1780,767,414|
1700,849,700|
820,1736,774|
621,1249,933|
346,1221,4|
17,535,994|
1472,910,265|
535,745,247|
1583,409,383|
1561,486,327|
819,666,759|
30,1482,498|
1719,161,643|
24,225,888|
1310,525,22|
983,297,881|
186,285,826|
579,836,290|
512,224,441|
1990,1516,535|
434,1549,58|
1531,1997,310|
1822,234,208|
998,766,757|
83,831,44|
1411,1386,456|
454,1171,421|
1529,1719,95|
1047,1150,242|
1524,1050,655|
1939,442,738|
1451,1309,209|
261,1067,39|
718,675,518|
892,241,48|
1643,1318,817|
1965,1623,830|
122,983,151|
1045,436,379|
458,3,850|
815,36,567|
155,1568,155|
902,1174,163|
614,68,760|
1371,1635,883|
47,346,355|
1202,687,995|
48,546,64|
1108,1302,486|
1852,9,978|
1486,696,852|
109,1880,296|
1794,1611,357|
387,280,109|
1329,1054,867|
529,164,807|
456,1332,768|
759,614,667|
1127,1533,912|
1108,1702,63|
507,1655,590|
1914,1812,352|
1213,787,299|
735,264,824|
61,375,153|
552,1819,589|
1215,1352,716|
97,1661,634|
1694,1550,652|
1461,1007,528|
1908,240,973|
781,622,300|
108,1011,45|
3,1054,902|
758,909,719|
1111,1136,286|
1859,643,295|
1555,348,409|
1916,359,336|
1562,1779,550|
711,514,118|
103,752,196|
1997,50,99|
1151,271,156|
308,799,930|
1279,493,369|
938,1836,292|
943,901,664|
1010,1345,532|
1119,608,427|
793,698,9|
1487,1689,240|
649,222,987|
1698,649,751|
1242,220,333|
883,658,93|
541,1217,685|
1519,1815,948|
80,1353,300|
1798,1389,683|
1154,364,470|
1045,654,319|
1048,852,833|
192,1855,362|
1023,652,469|
1391,1031,906|
1727,590,509|
1254,1366,92|
1381,120,997|
139,218,698|
1456,54,147|
1479,132,78|
1551,778,223|
1008,381,662|
1384,62,218|
474,1022,655|
1365,1620,260|
1492,993,301|
1784,12,748|
878,341,606|
444,426,652|
692,712,699|
1038,869,782|
1124,270,74|
1898,1203,777|
710,1328,883|
961,1209,731|
351,1156,725|
127,33,140|
3,1930,239|
1179,65,247|
449,1804,757|
1673,2,974|
1131,507,177|
1294,1240,893|
1851,607,499|
880,1548,943|
1361,1999,417|
1454,280,9|
1362,1299,416|
562,878,482|
1653,245,878|
681,1250,233|
37,1245,166|
300,1913,494|
1004,1592,964|
1820,798,84|
1906,972,330|
1259,924,292|
1911,1107,852|
776,1823,746|
1859,1321,1|
1926,1985,533|
1407,262,325|
823,1387,152|
1651,1694,578|
327,1652,894|
649,1613,207|
1867,466,524|
864,1036,231|
1783,805,649|
374,765,69|
635,1484,926|
1003,1093,973|
298,970,852|
1315,884,838|
1275,1412,212|
889,1950,391|
618,948,305|
55,178,183|
1603,221,41|
1619,124,196|
783,1867,27|
792,1446,51|
111,1093,967|
1089,93,397|
1257,1599,216|
1696,1953,158|
1289,1638,186|
1117,100,398|
1026,1114,807|
1003,1342,573|
615,1421,372|
476,1185,622|
1588,541,36|
1426,81,979|
56,758,579|
1923,901,226|
958,1544,562|
416,1017,195|
893,1401,913|
1855,245,352|
1816,1256,906|
1099,108,278|
1940,1394,863|];
plans=[|1568,1568|];